package Data_Structure.Tree.Heap;

import java.util.Arrays;

/**
 * @className: TestHeap
 * @author: 芃
 * @description: 模拟创建大根堆
 * @date: 2023/8/25 10:49
 */
public class TestBigHeap {
    public int[] elem;
    public int usedSize;

    public TestBigHeap() {
        this.elem = new int[10];
    }

    /**
     * @param array:
     * @author: zyp19
     * @description: 创建大根堆
     * @date: 2023/8/25 11:01
     */
    public void createBigHeap(int[] array){
        elem = Arrays.copyOf(array,array.length);
        this.usedSize = array.length;
        int parent = ((this.usedSize - 1) - 1) / 2;
        for (int i = parent; i >= 0; i--) {
            //将每个树的根节点传过去，以及调整结束的位置
            //调整结束的位置为整棵树的大小，即数组的大小
            shiftDown(i,this.usedSize);
        }
    }
    

    /**
     * @param parent: 每棵树的根节点
     * @param len: 每棵树的调整结束位置
     * @author: zyp19
     * @description: 向下调整
     * @date: 2023/8/25 11:00
     */
    public void shiftDown(int parent,int len){
        int child = 2*parent+1;
        //1、最起码是有左孩子的，至少有一个孩子
        while (child < len){
            if (child+1 < len && elem[child] < elem[child+1]){
                child++;//child下标保证当前左右孩子的最大值
            }
            //走到这，就找到了左右孩子的最大值
            if (elem[child] > elem[parent]){
                //交换
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                //交换完成后，需要继续向下调整，保证左右子树依然是大根堆
                parent = child;
                child = 2*parent + 1;
            }else {
                //说明左右孩子最大值依然没有根节点大
                break;
            }
        }
    }
    //建堆时间复杂度分析：O(N) 为什么？
    //我们假设此时有一颗满二叉树，即每层都放满了节点，共四层
    //然后根据上面的代码，我们可以看出，它的时间复杂度为每层节点的个数*向下调整的次数
    //即 (2^0 * 3) + (2^1 * 2) + (2^2 * 1) 依次类推，此处以4层举例，因此到第三层时就不用向下再调整了
    //假设时间复杂度用T（N）表示,高度用h表示
    //则 T（N） = 2^0*(h-1) + 2^1*(h-2) + 2^2*(h-3) + ...... + 2^(h-2)*1  表达式①
    //T（N）*2 = 2^1(h-1) + 2^2*(h-2) + 2^3*(h-3) + ...... + 2^(h-1)*1   表达式②
    //表达式② - 表达式① ->错位相减法
    //得
    //T（N） = -2^0*(h-1) + 2^1 + 2^2 + ...... + 2^(h-1)
    //      = 2^0 + 2^1 + 2^2 + ...... + 2^(h-1) - h
    // 等比数列求和
    // T（N） = 2^h - 1 - h
    //参考我们前面了解到的：一颗完全二叉树的节点个数N及其高度h的关系为：h = log2(n+1)向上取整
    //那么上面的表达式我们可以简化为：T(N) = 2^(log2(n+1)) - 1 - log2(n+1)
    //T(N) = n+1-1 - log2(n+1)
    //T(N) = n - log2(n+1)
    //众所周知，随着n的逐渐变大，log2(n+1)逐渐趋向于常树
    //因此，得出结论：O(N) = T(N) = N


    /**
     * @param val:
     * @author: zyp19
     * @description: 存放元素
     * @date: 2023/8/25 14:09
     */
    public void offer(int val){
        if (isFull()){//判满
            grow();//扩容
        }
        elem[usedSize] = val;
        usedSize++;
        //开始调整
        shiftUp(usedSize-1);
    }
    /**
     * @param child:
     * @author: zyp19
     * @description: 向上调整
     * @date: 2023/8/25 14:09
     */
    //问题：为什么发生交换之后就不用再向下调整了？
    //我们在存放元素的时候，此时堆已经是大根堆了，即任意root节点的值必大于其左右子节点的值
    //当发生交换后，把原parent的parent节点换下来，那也必然是大于原parent的左右子节点的
    //比较绕一点点？
    //              57
    //        48         36
    //     45    32    33   24
    //  18 40  27 19 22 11 8  17
    //看图，假设我们放一个49进来
    //49和18换->49把45换下来->49把48换下来
    //需要调整别的位置吗？
    //              57
    //        49         36
    //     48    32    33   24
    //  45 40  27 19 22 11 8  17
    // 18
    //换个简单点的术语，A是B的父节点，B是C的父节点，因为是大根堆，所以A必然是大于C的，因此只需要交换就行了，不需要关心堆的维护问题
    public void shiftUp(int child){
        int parent = (child-1) / 2;
        while (child > 0){
            //如果child大于parent就交换
            if (elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (parent - 1) / 2;
            }else {
                //说明child的值没有parent的值大，调整结束
                break;
            }
        }
    }

    /**
     * @return boolean
     * @author: zyp19
     * @description: 判断满
     * @date: 2023/8/25 14:10
     */
    public boolean isFull(){
        return this.usedSize == this.elem.length;
    }
    /**
     * @author: zyp19
     * @description: 扩容
     * @date: 2023/8/25 14:12
     */
    public void grow(){
        this.elem = Arrays.copyOf(this.elem,2*elem.length);
    }
    /**
     * @return int
     * @author: zyp19
     * @description: 查看堆顶元素
     * @date: 2023/8/25 14:33
     */
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException("堆为空");
        }else {
            return this.elem[0];
        }
    }
    /**
     * @return int
     * @author: zyp19
     * @description: 出堆，将堆顶的元素出出去
     * @date: 2023/8/25 14:34
     */
    public int poll(){
        if (isEmpty()){
            throw new RuntimeException("堆为空");
        }
        //①交换elem[0]和elem[usedSize-1]位置的元素
        int tmp = this.elem[0];
        this.elem[0] = this.elem[usedSize-1];
        this.elem[usedSize - 1] = tmp;
        //②交换完成后，下次存放元素时，会自动覆盖elem[usedSize]的值
        this.usedSize--;
        //③调整-》此时之后root这棵树是有问题的，因此，向下调整root这棵树即可
        shiftDown(0,this.usedSize);
        return tmp;
    }
    /**
     * @return boolean
     * @author: zyp19
     * @description: 判断空
     * @date: 2023/8/25 14:35
     */
    public boolean isEmpty(){
        return this.usedSize == 0;
    }
    /**
     * @author: zyp19
     * @description: 堆排序，从小到大
     * @date: 2023/8/25 15:41
     */
    public void heapSort(){
        int end = this.usedSize - 1;
        while (end > 0){
            //①交换0下标元素和数组末尾元素
            swap(0,end);
            //②向下调整0下标这棵树->调整到end位置
            //为什么是end而不是end-1？
            //我们的第二个参数代表调整结束的位置，比如10个元素，此时end就等于9，参考shiftDown函数，调整到8位置就结束了，因此不需要-1
            shiftDown(0,end);
            //③end--
            end--;
        }
    }
    public void swap(int i,int j){
        int tmp = this.elem[i];
        this.elem[i] = this.elem[j];
        this.elem[j] = tmp;
    }
}
